<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>向量相似度搜索 - 算法深度解析</title>
    <link href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css" rel="stylesheet">
    <link href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css" rel="stylesheet">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
            background: linear-gradient(135deg, #f5f7fa 0%, #c3cfe2 100%);
            min-height: 100vh;
        }
        
        .hero-gradient {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
        }
        
        .card-hover {
            transition: all 0.3s ease;
            border: 1px solid transparent;
        }
        
        .card-hover:hover {
            transform: translateY(-5px);
            box-shadow: 0 20px 40px rgba(0,0,0,0.1);
            border-color: #667eea;
        }
        
        .code-container {
            background: #1e1e1e;
            border-radius: 12px;
            overflow: hidden;
            box-shadow: 0 10px 30px rgba(0,0,0,0.2);
        }
        
        .code-header {
            background: #2d2d2d;
            padding: 10px 20px;
            display: flex;
            align-items: center;
            gap: 8px;
        }
        
        .code-dot {
            width: 12px;
            height: 12px;
            border-radius: 50%;
        }
        
        pre {
            margin: 0;
            padding: 20px;
            overflow-x: auto;
            color: #d4d4d4;
            font-size: 14px;
            line-height: 1.6;
        }
        
        .highlight-gradient {
            background: linear-gradient(90deg, #667eea, #764ba2);
            -webkit-background-clip: text;
            -webkit-text-fill-color: transparent;
            background-clip: text;
        }
        
        .section-divider {
            height: 2px;
            background: linear-gradient(90deg, transparent, #667eea, transparent);
            margin: 3rem 0;
        }
        
        .floating-icon {
            animation: float 3s ease-in-out infinite;
        }
        
        @keyframes float {
            0%, 100% { transform: translateY(0px); }
            50% { transform: translateY(-10px); }
        }
        
        .mermaid {
            display: flex;
            justify-content: center;
            margin: 2rem 0;
        }
        
        .drop-cap {
            float: left;
            font-size: 4rem;
            line-height: 1;
            font-weight: 700;
            margin-right: 0.5rem;
            color: #667eea;
            font-family: 'Noto Serif SC', serif;
        }
    </style>
</head>
<body>
    <!-- Hero Section -->
    <section class="hero-gradient text-white py-20 px-6">
        <div class="max-w-6xl mx-auto text-center">
            <div class="floating-icon inline-block mb-6">
                <i class="fas fa-project-diagram text-6xl opacity-80"></i>
            </div>
            <h1 class="text-5xl md:text-6xl font-bold mb-6 tracking-tight">
                向量相似度搜索
            </h1>
            <p class="text-xl md:text-2xl opacity-90 max-w-3xl mx-auto leading-relaxed">
                探索高维空间中的智能检索技术，掌握 KD 树与局部敏感哈希的精髓
            </p>
        </div>
    </section>

    <!-- Main Content -->
    <main class="max-w-6xl mx-auto px-6 py-12">
        <!-- Problem Description Card -->
        <div class="bg-white rounded-2xl shadow-xl p-8 mb-8 card-hover">
            <div class="flex items-center mb-4">
                <i class="fas fa-question-circle text-3xl text-purple-600 mr-4"></i>
                <h2 class="text-3xl font-bold text-gray-800">问题描述</h2>
            </div>
            <p class="text-lg text-gray-700 leading-relaxed">
                <span class="drop-cap">给</span>定一组高维向量和一个查询向量，如何高效地在数据集中查找与查询向量最相似的向量？这是机器学习、推荐系统、图像检索等领域的核心问题。
            </p>
        </div>

        <!-- Core Concepts -->
        <div class="grid md:grid-cols-2 gap-8 mb-12">
            <div class="bg-white rounded-2xl shadow-xl p-8 card-hover">
                <div class="flex items-center mb-6">
                    <i class="fas fa-tree text-3xl text-green-600 mr-4"></i>
                    <h3 class="text-2xl font-bold text-gray-800">KD 树</h3>
                </div>
                <p class="text-gray-700 mb-4">
                    构建多维空间的二叉树结构，通过空间划分实现高效的最近邻搜索。
                </p>
                <div class="bg-gray-50 rounded-lg p-4 mt-4">
                    <div class="flex items-center justify-between text-sm">
                        <span class="text-gray-600"><i class="fas fa-clock mr-2"></i>时间复杂度</span>
                        <span class="font-mono font-bold text-green-600">O(log n)</span>
                    </div>
                    <div class="flex items-center justify-between text-sm mt-2">
                        <span class="text-gray-600"><i class="fas fa-memory mr-2"></i>空间复杂度</span>
                        <span class="font-mono font-bold text-blue-600">O(n)</span>
                    </div>
                </div>
            </div>

            <div class="bg-white rounded-2xl shadow-xl p-8 card-hover">
                <div class="flex items-center mb-6">
                    <i class="fas fa-hashtag text-3xl text-indigo-600 mr-4"></i>
                    <h3 class="text-2xl font-bold text-gray-800">局部敏感哈希 (LSH)</h3>
                </div>
                <p class="text-gray-700 mb-4">
                    通过哈希函数将相近向量映射到相同桶中，实现近似最近邻的快速检索。
                </p>
                <div class="bg-gray-50 rounded-lg p-4 mt-4">
                    <div class="flex items-center justify-between text-sm">
                        <span class="text-gray-600"><i class="fas fa-clock mr-2"></i>时间复杂度</span>
                        <span class="font-mono font-bold text-green-600">O(1)</span>
                    </div>
                    <div class="flex items-center justify-between text-sm mt-2">
                        <span class="text-gray-600"><i class="fas fa-memory mr-2"></i>空间复杂度</span>
                        <span class="font-mono font-bold text-blue-600">O(n)</span>
                    </div>
                </div>
            </div>
        </div>

        <div class="section-divider"></div>

        <!-- Algorithm Visualization -->
        <section class="mb-12">
            <h2 class="text-3xl font-bold text-gray-800 mb-8 text-center">
                <i class="fas fa-sitemap mr-3 text-purple-600"></i>算法架构图
            </h2>
            <div class="bg-white rounded-2xl shadow-xl p-8">
                <div class="mermaid">
                    graph TD
                        A[查询向量] --> B{相似度搜索}
                        B --> C[KD树方法]
                        B --> D[LSH方法]
                        C --> E[空间划分]
                        C --> F[树遍历]
                        C --> G[精确搜索]
                        D --> H[哈希映射]
                        D --> I[桶检索]
                        D --> J[近似搜索]
                        E --> K[最近邻结果]
                        F --> K
                        G --> K
                        H --> L[候选集合]
                        I --> L
                        J --> L
                        L --> M[相似度计算]
                        M --> N[Top-K结果]
                        
                        style A fill:#667eea,stroke:#fff,stroke-width:3px,color:#fff
                        style K fill:#10b981,stroke:#fff,stroke-width:3px,color:#fff
                        style N fill:#10b981,stroke:#fff,stroke-width:3px,color:#fff
                </div>
            </div>
        </section>

        <!-- Code Implementation -->
        <section class="mb-12">
            <h2 class="text-3xl font-bold text-gray-800 mb-8">
                <i class="fas fa-code mr-3 text-purple-600"></i>核心实现
            </h2>
            <div class="code-container">
                <div class="code-header">
                    <div class="code-dot bg-red-500"></div>
                    <div class="code-dot bg-yellow-500"></div>
                    <div class="code-dot bg-green-500"></div>
                    <span class="text-gray-400 ml-4 text-sm">VectorSimilaritySearch.java</span>
                </div>
                <pre><code>import java.util.*;

/**
 * 向量相似度搜索工具类
 * 提供计算向量相似度和查找最相似向量的方法
 */
public class VectorSimilaritySearch {
    
    /**
     * 计算两个向量之间的余弦相似度
     * 余弦相似度 = 向量点积 / (向量1范数 * 向量2范数)
     * 
     * @param vec1 第一个向量
     * @param vec2 第二个向量
     * @return 两个向量的余弦相似度，范围[-1,1]，值越大表示越相似
     */
    public static double cosineSimilarity(double[] vec1, double[] vec2) {
        // 确保两个向量长度相同
        if (vec1.length != vec2.length) {
            throw new IllegalArgumentException("向量维度不匹配");
        }
        
        // 计算点积
        double dotProduct = 0.0;
        for (int i = 0; i < vec1.length; i++) {
            dotProduct += vec1[i] * vec2[i];
        }
        
        // 计算向量范数
        double norm1 = 0.0;
        double norm2 = 0.0;
        for (int i = 0; i < vec1.length; i++) {
            norm1 += vec1[i] * vec1[i];
            norm2 += vec2[i] * vec2[i];
        }
        norm1 = Math.sqrt(norm1);
        norm2 = Math.sqrt(norm2);
        
        // 避免除以零
        if (norm1 == 0.0 || norm2 == 0.0) {
            return 0.0;
        }
        
        // 返回余弦相似度
        return dotProduct / (norm1 * norm2);
    }
    
    /**
     * 在向量集合中查找与查询向量最相似的k个向量
     * 
     * @param vectors 向量集合
     * @param query 查询向量
     * @param k 返回的最相似向量数量
     * @return 最相似的k个向量的索引列表
     */
    public static List<Integer> findMostSimilar(List<double[]> vectors, double[] query, int k) {
        // 存储每个向量的索引及其与查询向量的相似度
        PriorityQueue<Map.Entry<Integer, Double>> pq = new PriorityQueue<>(
                (a, b) -> Double.compare(a.getValue(), b.getValue()));
        
        // 计算每个向量与查询向量的相似度
        for (int i = 0; i < vectors.size(); i++) {
            double similarity = cosineSimilarity(vectors.get(i), query);
            
            // 维护大小为k的优先队列
            if (pq.size() < k) {
                pq.offer(new AbstractMap.SimpleEntry<>(i, similarity));
            } else if (similarity > pq.peek().getValue()) {
                pq.poll();
                pq.offer(new AbstractMap.SimpleEntry<>(i, similarity));
            }
        }
        
        // 按相似度从高到低排序结果
        List<Integer> result = new ArrayList<>();
        while (!pq.isEmpty()) {
            result.add(0, pq.poll().getKey());
        }
        
        return result;
    }
    
    /**
     * KD树节点类
     */
    static class KDNode {
        double[] point;
        int axis;
        KDNode left;
        KDNode right;
        
        public KDNode(double[] point, int axis) {
            this.point = point;
            this.axis = axis;
        }
    }
    
    /**
     * 构建KD树
     * 
     * @param points 点集合
     * @param depth 当前深度
     * @param k 维度
     * @return KD树根节点
     */
    public static KDNode buildKDTree(List<double[]> points, int depth, int k) {
        if (points.isEmpty()) {
            return null;
        }
        
        // 选择划分维度
        int axis = depth % k;
        
        // 按当前维度排序点
        int medianIdx = points.size() / 2;
        points.sort(Comparator.comparingDouble(point -> point[axis]));